package 我的Java学习_算法基础.day_07;

import java.util.ArrayList;

import static java.lang.System.exit;

/**
 * @author 挚爱之夕
 * @date 2021/8/21 - 08 - 21 - 14:59
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _116_部分和 {
    public static void main(String[] args) {
        int[] a = {1,3,5,6};
        subsets(a,12);


        int k = 11;
        kk=k;
        dfs(a,k,0);

    }

    /**
     * 二进制法
     * @param a 指定数组
     * @param k 和
     */
    private static void subsets(int[] a,int k){
        StringBuilder sb = new StringBuilder("Yes ("+k+" = ");
        int length = a.length;
        int sum = 0;
        for(int i = 1;i<(int)Math.pow(2,length);i++){
            ArrayList<Integer> list = new ArrayList<>();
            for(int j =0;j<length;j++){
                if(((i>>j)&1)==1){
                    list.add(a[j]);
                    sum+=a[j];
                }
            }
            if(sum==k){
                for (int j = 0; j < list.size()-1; j++) {
                    sb.append(list.get(j)+" ").append('+');
                }
                sb.append(" "+list.get(list.size()-1)).append(")");
                System.out.println(sb);
                return;
            }
            sum=0;
        }
        System.out.println("No Find!");
    }

    /**
     * 深搜
     * @param a 指定数组
     * @param k 和
     * @param cur 当前下标
     */

    static ArrayList<Integer> ints = new ArrayList<>();
    static int kk;  //记录所求和的值

    private static void dfs(int[] a,int k,int cur){
        if(k==0){
            System.out.print("Yes ("+kk+" = ");
            int size = ints.size();
            for(int i = 0;i<size;i++){
                System.out.print(ints.get(i)+(i==size-1?"":" + "));
            }
            System.out.println(")");
            exit(0);
        }
        if(k<0||cur==a.length) return;
        //不要当前元素
        dfs(a,k,cur+1);
        //要当前元素
        ints.add(a[cur]);
        int index = ints.size() - 1;
        dfs(a,k-a[cur],cur+1);
        ints.remove(index);//回溯
    }
}
